1. Field of the Invention
This invention relates to a system and method for navigation and route guidance by an object, person or vehicle along a network.
2. Description of the Related Art
To successfully reach a destination one must find a way there, with sufficient efficiency so the value of the journey exceeds its cost. A variety of systems and devices have been invented to assist in this task: line-of-sight, maps, directions, compass, and sextant, to name a few. Many of these systems and devices have been adapted to the computer, and new systems have been and are being developed.
A special case of finding one's way is when travel is constrained to the links and intersections of a network. This is typically the case in travel on land, where one can quickly get in trouble by straying from the path or road. Except for sailors and astronauts, most humans (and many animals) travel predominantly on networks and navigate along those networks.
A number of computerized systems have been developed to aid in navigation, route finding, and route guidance along networks. The currently available systems can be classified into three types. First-generation systems provide a map and the ability to view and interrogate the map. Second-generation systems extend this with an automated determination of current location, typically by means of a global positioning system (GPS) receiver, and an automated display of this location on the map. Third-generation systems issue turn-by-turn directions to the user's destination, by finding the user's current location and destination on the network, and calculating a recommended route in between.
All three types of systems have been implemented in stand-alone configurations and in client/server configurations. In a stand-alone configuration, a single computer contains sufficient resources to store all the necessary map data and perform all the necessary calculations. In a client/server configuration, this work is split between at least two computers, a client and a server, connected by a means of communication. Client/server configurations can be either thick-client, in which most of the data and calculations are on the clients, or thin-client, in which most of the data and calculations are on the server.
Since the server does most of the work in a thin-client configuration, the client computer can be relatively small, low-powered, and inexpensive. This is an attractive goal for a mobile application such as route guidance. However, the client is then dependent on reliable and responsive wireless communication with the server. Unfortunately, wireless data communication is relatively unreliable, due to gaps caused by poor reception; unresponsive, due to delays in switching packets through the network; and expensive. As a result, existing third-generation thin-client navigation systems perform poorly compared to their stand-alone equivalents, because they are unable to reliably and quickly find routes when the user deviates from the route (e.g., when the user misses a turn, or is forced to detour).
On the other hand, stand-alone systems suffer from lack of current knowledge of traffic congestion; weather (ice, snow, high winds, etc.); new, closed, or improved roads; and other temporal information valuable to finding good routes, and require larger, more expensive, more power-consuming client computers.
Thick-client systems suffer from either being prohibitively slow or requiring prohibitively expensive communications bandwidth, and also require larger, more expensive, more power-consuming client computers.
For these reasons, a thin-client navigation system is desirable, if a method can be found to efficiently buffer a sufficient portion of the map data and calculation on the client device, so it can continue to provide guidance if the user deviates from the recommended route, despite brief delays or interruptions in communication with the server.
U.S. Pat. No. 6,052,645 describes a system in which a client permanently stores a map of main roads and requests detailed maps from a server as needed. The client performs route calculations using the maps. This is a thick-client system because the client must have significant storage capacity to permanently store a map of main roads and a powerful processor to perform route calculations. When the client detects a deviation from route it requests from the server a detailed map around the point of deviation that the client can use to calculate a new route. Given that the necessary mobile communication network has slow throughput and is likely to be interrupted, and that significant time is required to calculate a new route once the detailed map data is received, a user of this system is likely to have to wait an unacceptably long amount of time before the detailed map is displayed and/or new turn instructions are available.
U.S. Pat. No. 6,107,944 describes a system in which map storage and route calculation is performed by a server that communicates compact maneuver (turn) instructions to a client. This is a thin-client system because the client will need only minimal storage to hold the compact turn instructions and a minimal processor to display them. The turn instructions provided to the client might be used to detect deviation from route, if provided in sufficient detail. However, once deviation is detected, the client would need to wait to receive a new set of instructions from the server. A user of this system would either not have the benefit of route deviation detection, or would have to wait an unacceptably long amount of time before new turn instructions would be available.
The following U.S. patents are cited for their general discussion of navigation and route guidance systems of possible relevance: U.S. Pat. Nos. 5,177,685; 5,293,163; 5,652,706; 5,675,492; 5,862,509; 5,875,412; 5,893,081; 5,916,299; 6,014,607; 6,016,485; 6,038,509; 6,064,941; 6,070,122; 6,192,313; 6,192,314; 6,199,009; 6,199,013; 6,211,798.